#!/usr/bin/python
#-*- coding:utf-8 -*-
# Description:  <C程序设计竞赛实训教程> 刘高军、何丽 编著 第11.1节：石油探测
#          '@'表示有石油， '*'表示没有石油， 求连在一起的石油的块数。
#          用深度和广度搜索来解决
import numpy as np
from pprint import pprint

direction = set([(i,j) for i in [-1, 0, 1] for j in [-1, 0, 1]])
direction.remove((0,0)) # 周边8个方向的坐标增量

def dfs(r, axis, flag):
    i, j = axis
    flag[i][j] = False
    for d in direction:
        new_i, new_j = i+d[0], j+d[1] # 相邻坐标
        if 0 <= new_i < flag.shape[0] and 0 <= new_j < flag.shape[1] \
           and flag[new_i][new_j] and r[new_i][new_j] == '@' :
            dfs(r, (new_i, new_j), flag) #递归进行
    return

def bfs(r, axis, flag):
    i, j = axis
    flag[i][j] = False

    queue = [axis]
    while queue :
        i, j = queue.pop(0)
        for d in direction:
            new_i, new_j = i+d[0], j+d[1] # 相邻坐标
            if 0 <= new_i < flag.shape[0] and 0 <= new_j < flag.shape[1] \
               and flag[new_i][new_j] and r[new_i][new_j] == '@' :
                flag[new_i][new_j] = False
                queue.append( (new_i, new_j) )
    return


def search(r):
    num = 0
    flag = np.ones_like(r, dtype=bool)
    for i in range(flag.shape[0]):
        for j in range(flag.shape[1]):
            if r[i][j] == '@' and flag[i][j] :
                num += 1
                bfs(r, (i,j), flag) # dfs(r, (i,j), flag) 

    return num

rect = ['****@',
        '*@@*@',
        '*@**@',
        '@@@*@',
        '@@**@',
        '*@*@*',
]

r = np.array([list(r) for r in rect])
pprint(r)
print( search(r) )
